LeetCode 215. Kth Largest Element in an Array

鐵人賽程式設計 12th鐵人賽 13th鐵人賽 2019鐵人賽

John Lu

團隊捲土重來的Kotlin鐵人們

2023-09-29 08:27:30

560 瀏覽

分享至

破題

假設：陣列的長度為 $n$ 。
題意：這題是希望我們找出一個整數陣列中第 $n$ 大的數字。

方法一：計數排序 (Counting Sort)

解題思路

首先，我們遍歷整個陣列，找出最小和最大的數字。
然後，我們宣告一個計數陣列，其大小為最大數字和最小數字之間的範圍加一。每個元素的初始值都設為 0。
再次遍歷原始陣列，對每個數字出現的次數進行計數。計數的方式是將該數字減去最小值，然後在計數陣列中對應的位置加一。
從計數陣列的尾端開始向前遍歷，直到找到第 $n$ 大的數字。

跟一流的人才幹大事，享受成功進步的高級樂趣！
內推機會來啦！能與優秀的程式設計師共事，是特別痛快的事，因為厲害的工程師大神會刺激你想要迎頭趕上的上進心，尤其是一起討論解決方案時，他們會觸發你有更好的解決思維能力，彼此共同成長並且一起享受解謎與破關般的樂趣。你一定聽得懂我在說甚麼感覺，趕快把握機會，動動手指投遞履歷吧！立即加入「面試讀書會」，和大家一起準備面試！

　內推機會 　加入讀書會 (邀請碼：4886)

程式

class Solution {
    fun findKthLargest(nums: IntArray, k: Int): Int {
        var min = 0
        var max = 0
        nums.forEach {
            if (it < min) min = it
            if (it > max) max = it
        }
        val counts = IntArray(max - min + 1) { 0 }
        nums.forEach {
            counts[it - min]++
        }
        var remains = k
        var ans = nums[0]
        for (i in counts.size - 1 downTo 0) {
            val count = counts[i]
            if (remains - count > 0) {
                remains -= count
            } else {
                ans = i + min
                break
            }
        }
        return ans
    }
}

複雜度分析

時間複雜度:
$N$ ，其中 $n$ 為原始陣列的大小。我們需要遍歷原始陣列兩次，一次是找出最大和最小值，另一次是進行計數。然後我們還需要遍歷計數陣列來找出第 $n$ 大的數字。但由於我們只遍歷每個陣列一次，所以時間複雜度為 $N$ 。
空間複雜度:
$N$ ，其中 $n$ 為最大和最小值之間的範圍。我們需要宣告一個大小為 $n$ 的計數陣列來存儲每個數字出現的次數。因此，空間複雜度為 $N$ 。
但如果 $n$ 遠大於 $n$ ，則空間複雜度可能會成為問題。在這種情況下，我們可能需要使用其他方法來解決這個問題。例如，我們可以使用「快速排序 (Quick Sort)」的演算法來在 $N$ 時間內找到第 $n$ 大的元素，這樣只需要常數量級的空間。